package algorithm.tree;

import algorithm.model.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * leetcode : https://leetcode.com/problems/binary-tree-level-order-traversal/description/
 * Difficulty : Medium
 *
 * 思路：
 * 树的广度优先遍历
 * @Author Antony
 * @Since 2018/7/19 19:51
 */
public class BinaryTreeLevelOrderTraversal {


    /**
     * beats 85.75% - 1ms
     * 思路:
     * 还是链表迭代，但是具体使用Queue，实现类为LinkedList
     * 方法为 add 和 poll
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;    // 需要返回空 而不是null

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int currSize = 1;
        int nextSize = 0;
        List<Integer> list = new ArrayList<>(1);
        while(currSize > 0){
            TreeNode node = queue.poll();
            list.add(node.val);
            currSize--;
            if(node.left != null){
                queue.add(node.left);
                nextSize++;
            }
            if(node.right != null){
                queue.add(node.right);
                nextSize++;
            }

            // 换为下一层
            if(currSize == 0) {
                currSize = nextSize;
                nextSize = 0;
                // 把当层数据加进结果，初始化下一层数据
                result.add(list);
                list = new ArrayList<>(currSize);
            }
        }

        return result;
    }


    /**
     * 会报Memory Limit Exceeded
     * 由于不断创建列表，空间使用太大
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder_memoryLimit(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;    // 需要返回空 而不是null

        List<TreeNode> currNodeList = new ArrayList<>();
        currNodeList.add(root);
        int levelSize =1;

        while(currNodeList.size() > 0){
            List<Integer> levelList = new ArrayList<>(levelSize);
            levelSize *= 2;
            List<TreeNode> levelNode = new ArrayList<>(levelSize);
            for(TreeNode node : currNodeList){
                levelList.add(node.val);
                if(node.left != null) levelNode.add(node.left);
                if(node.right != null) levelNode.add(node.right);
            }
            result.add(levelList);
            currNodeList = levelNode;
        }

        return result;
    }
}
